1. Field
The present invention generally relates to techniques for performing static timing analysis (STA) for integrated circuit (IC) chips. More specifically, the present invention relates to a method and an apparatus for performing an efficient exhaustive path-based STA by using a fast path-delay-estimation.
2. Related Art
Rapid advances in computing technology have made it possible to perform trillions of computational operations each second on data sets that are sometimes as large as trillions of bytes. These advances can be largely attributed to the exponential increase in the size and complexity of integrated circuits.
Due to the increase in size and complexity of integrated circuits, it has become necessary to use sophisticated tools to verify timing constraints.
Before the advent of Static Timing Analysis (STA), timing constraints were typically verified using simulation-based techniques. As the complexity of integrated circuits grew, using simulation-based techniques to verify timing constraints became impractical because of their long runtimes, low capacities, and incomplete analyses.
Unlike simulation-based techniques, STA verifies timing by computing the worst-case and the best-case delays without enumerating all possible paths. Because of this, STA can perform a thorough timing analysis for large integrated circuits within a reasonable amount of time. As a result, STA has emerged as the method of choice for verifying timing constraints for large integrated circuits.
During the STA stage of the integrated circuit (IC) design, both a graph-based STA and a path-based analysis are often used. A graph-based STA is very fast (O(N); N is the number of cells in a design), but the results are often pessimistic. A path-based STA is typically used to provide less pessimistic (and more accurate) estimates for timing slacks (or “slacks”) than a graph-based STA. More specifically, path-based analysis is often performed after graph-based analysis by ordering the results from graph-based analysis, starting from the most pessimistic endpoint, and recomputing the slack to that endpoint for each path that terminates there. Path-based slacks are generally less pessimistic because they do not use the worst slew at each merge point in the timing graph, as required by graph-based analysis, but the relative improvement for each endpoint may vary.
Unfortunately, path-based STA is a computationally intensive process which can require tracing every possible path within a design. Although path-based STA is accurate, the amount of computation required to perform path-based STA can increase exponentially with the number of cells.
Hence, what is needed is a method and an apparatus that can reduce the runtime associated with an exhaustive path-based STA.